package everyday;

/**
 * @author zhangmin
 * @create 2022-04-25 11:03
 *
 * 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
 * 思路：
 * dp[i]表示以i为结尾的最长合法括号子串长度
 * 只在遇到）的时候才有可能是合法的
 */
public class longestValidParentheses32 {
    public int longestValidParentheses(String s) {
        int n=s.length();
        if (n<=1) return 0;
        int[] dp=new int[n];
        int res=0;
        for (int i = 1; i < n; i++) {
            if (s.charAt(i)==')'){
                if(s.charAt(i-1)=='('){
                    //遇到的是...()的情况
                    dp[i]=(i-2>=0?dp[i-2]:0)+2;
                }else {
                    //遇到的是...))的情况，需要判断之前的
                    if (i-dp[i-1]-1>=0&&s.charAt(i-dp[i-1]-1)=='('){
                        dp[i]=(i-dp[i-1]-2>=0?dp[i-dp[i-1]-2]:0)+dp[i-1]+2;
                    }
                }
                res=Math.max(res,dp[i]);
            }
        }
        return res;
    }
}
